/********************************************************************************
* @author: Liu  HZ
* @date: 2024/9/21
* @description: 
********************************************************************************/

#ifndef THE_PATH_OF_CPP_CODE_H
#define THE_PATH_OF_CPP_CODE_H

#include <iostream>
#include <string>
#include <set>
#include <unordered_set>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <stack>

using namespace std;

////////////////////////////////////////////////哈希类型//////////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
 * 1. 两数之和
 */
vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hashMap;

    for (int i = 0; i < nums.size(); i++) {
        auto iter = hashMap.find(target - nums[i]);

        if (iter != hashMap.end())
            return {iter->second, i};

        hashMap[nums[i]] = i;
    }

    return {};
}

/*
 * https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
 * 49. 字母异位词分组
 */
vector<vector<string>> groupAnagrams(vector<string> &strs) {
    vector<vector<string>> ans;
    if (strs.size() == 1)
        return {
                {strs[0]}
        };

    unordered_map<string, vector<string>> temp;
    for (const string &s: strs) {
        string key = s;
        std::sort(key.begin(), key.end());
        temp[key].emplace_back(s);
    }

    for (auto &a: temp) {
        ans.push_back(a.second);
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
 * 128. 最长连续序列
 */
int longestConsecutive(vector<int> &nums) {
    std::set<long> tempSet;

    for (long num: nums) {
        tempSet.insert(num);
    }

    int ansMax = 0, index = 0;
    bool isContinues = true;

    if (!tempSet.empty()) {
        auto it = tempSet.begin();
        while (it != tempSet.end()) {
            index++;
            if (std::next(it) == tempSet.end())
                break;
            if (std::abs(*it - *std::next(it)) != 1) {
                isContinues = false;
                if (index > ansMax) {
                    ansMax = index;
                }
                index = 0;
            }

            ++it;
        }
    }

    if (isContinues)
        ansMax = static_cast<int>(tempSet.size());
    return ansMax < index ? index : ansMax;
}
/////////////////////////////////////////////////双指针类型///////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
 * 283. 移动零
 */
void moveZeroes(vector<int> &nums) {

    for (int i = 0, k = 0; i < nums.size(); ++i) {
        if (nums[i]) {
            swap(nums[i], nums[k++]);
        }
    }
}

/*
 * https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-100-liked
 * 11. 盛最多水的容器
 */
int maxArea(vector<int> &height) {
    int ans = 0, l = 0, r = height.size() - 1;
    while (l < r) {
        ans = std::max(ans, std::min(height[l], height[r]) * (r - l));
        if (height[l] < height[r])
            l++;
        else
            r--;
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked
 * 15. 三数之和
 * 题解: https://leetcode.cn/problems/3sum/solutions/11525/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/?envType=study-plan-v2&envId=top-100-liked
 */
vector<vector<int>> threeSum(vector<int> &nums) {
    // 递增排序方便判重+过滤 时间复杂度 nlogn
    sort(nums.begin(), nums.end());

    vector<vector<int>> ans;
    for (int i = 0; i < nums.size() - 2; ++i) {

        if (nums[i] > 0) return ans;
        if (i > 0 && nums[i] == nums[i - 1])
            continue;

        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            // sum > 0: 最右端的数大了,往左边去重探测
            if (sum > 0) {
                right--;
                while (left < right && nums[right] == nums[right + 1])
                    right--;
            } else if (sum < 0) {
                left++;
                while (left < right && nums[left] == nums[left - 1])
                    left++;
            } else {
                // sum 相等,则记录答案
                ans.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1])
                    left++;
                while (left < right && nums[right] == nums[right + 1])
                    right--;
            }
        }
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
 * 42. 接雨水
 * 题解:
 */
int trap(vector<int> &height) {
    int ans = 0;
    stack<int> stk;
    int n = height.size();
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && height[i] > height[stk.top()]) {
            int top = stk.top();
            stk.pop();
            if (stk.empty()) {
                break;
            }
            int left = stk.top();
            int currWidth = i - left - 1;
            int currHeight = min(height[left], height[i]) - height[top];
            ans += currWidth * currHeight;
        }
        stk.push(i);
    }
    return ans;
}
/////////////////////////////////////////////////滑动窗口类型/////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
 * 3. 无重复字符的最长子串
 */
int lengthOfLongestSubstring(string s) {
    // 哈希集合: 记录每个元素是否出现过
    unordered_set<char> occ;
    int n = s.size();
    // 右指针: 初始值为 -1, 相当于我们在字符串的左边界的左侧, 还没有开始移动
    int rk = -1, ans = 0;
    // 枚举左指针的位置,初始值隐性地表示为 -1
    for (int i = 0; i < n; ++i) {
        if (i != 0) {
            occ.erase(s[i - 1]);
        }
        while (rk + 1 < n && !occ.count(s[rk + 1])) {
            // 不断地移动右指针
            occ.insert(s[rk + 1]);
            ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1);
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
 * 438. 找到字符串中所有字母异位词
 */
vector<int> findAnagrams(string s, string p) {
    int sLen = s.size(), pLen = p.size();
    if (sLen < pLen)
        return {};

    vector<int> ans;
    vector<int> sCount(26);
    vector<int> pCount(26);

    for (int i = 0; i < pLen; i++) {
        sCount[s[i] - 'a']++;
        pCount[p[i] - 'a']++;
    }

    if (sCount == pCount)
        ans.emplace_back(0);

    for (int i = 0; i < sLen - pLen; ++i) {
        sCount[s[i] - 'a']--;
        sCount[s[i + pLen] - 'a']++;

        if (sCount == pCount)
            ans.emplace_back(i + 1);
    }

    return ans;
}
///////////////////////////////////////////////////子串类型///////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
 * 560. 和为 K 的子数组
 */
int subarraySum(vector<int> &nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int preSum = 0, ans = 0;

    for (auto a: nums) {
        preSum += a;

        if (mp.find(preSum - k) != mp.end()) {
            ans += mp[preSum - k];
        }

        mp[preSum]++;
    }

    return ans;
}

///////////////////////////////////////////////////普通数组类型///////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
 * 53. 最大子数组和 dp问题
 */
int maxSubArray(vector<int> &nums) {
    int pre = 0, maxAns = nums[0];

    for (const auto &x: nums) {
        pre = max(pre + x, x);
        maxAns = max(pre, maxAns);
    }

    return maxAns;
}

/*
 * https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
 * 56. 合并区间
 */
vector<vector<int>> merge(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> ans;

    for (int i = 0; i < intervals.size();) {
        int rightMax = intervals[i][1];
        int next = i + 1;
        while (next < intervals.size() && intervals[next][0] <= rightMax) {
            rightMax = max(intervals[next][1], rightMax);
            next++;
        }

        ans.push_back({intervals[i][0], rightMax});
        i = next;
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
 * 189. 轮转数组
 */
void rotate(vector<int> &nums, int k) {
    k = k % nums.size();
    std::reverse(nums.begin(), nums.end());
    std::reverse(nums.begin(), nums.begin() + k);
    std::reverse(nums.begin() + k, nums.end());
}

/*
 * https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
 * 238. 除自身以外数组的乘积
 */
vector<int> productExceptSelf(vector<int> &nums) {
    vector<int> ans(nums.size());
    ans[0] = 1;
    for (int i = 1; i < nums.size(); ++i) {
        ans[i] = ans[i - 1] * nums[i - 1];
    }

    int temp = 1;
    for (int i = nums.size() - 2; i >= 0; --i) {
        temp = temp * nums[i + 1];
        ans[i] = ans[i] * temp;
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
 * 41. 缺失的第一个正数
 */

////////////////////////////////////////////////矩阵 类型//////////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
 * 73. 矩阵置零
 */
void setZeroes(vector<vector<int>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> row(m), col(n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!matrix[i][j]) {
                row[i] = col[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}








#endif //THE_PATH_OF_CPP_CODE_H
